/**
 * 3. 无重复字符的最长子串
 * https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 */
public class Solutions_3 {
    public static void main(String[] args) {
//        String s = "abcabcbb";  // output: 3
//        String s = "bbbbb";  // output: 1
        String s = "pwwkew";  // output: 3

        int result = lengthOfLongestSubstring(s);
        System.out.println(result);
    }

    public static int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() < 1) {
            return 0;
        }
        // map[97] = 1:表示在滑动窗口 [left, right] 中，字符 a 出现了 1 次
        int[] map = new int[128];
        char[] sarr = s.toCharArray();

        int len = sarr.length, left = 0, right = 0;
        int res = 0;

        while (right < len) {
            char c = sarr[right];
            map[c] ++;
            while (map[c] > 1) {
                // 左指针右移，直到 [left, right] 窗口中，不包含重复的字符时
                char k = sarr[left];
                map[k] --;
                left ++;
            }
            // 记录最大窗口长度
            res = Math.max(res, right - left + 1);
            // 每次窗口右指针右移一个单位
            right ++;
        }
        return res;
    }
}
